package org.example.myleet.p1175;

public class Solution {

    private static final int MOD_BASE = 1000000007;

    private static final int DEFAULT = 0;
    private static final int PRIME = 1;
    private static final int NORMAL = 2;

    public int numPrimeArrangements(int n) {
        if (n <= 2) {
            return 1;
        }
        int[] numberClass = new int[n + 1];
        findAllPrime(numberClass);
        int nPrime = 0;
        int nNormal = 0;
        for (int i = 1; i <= n; ++i) {
            if (numberClass[i] == NORMAL) {
                ++nNormal;
            } else {
                ++nPrime;
            }
        }
        long sum = 1;
        for (int i = nNormal; i > 1; --i) {
            sum *= i;
            sum = sum % MOD_BASE;
        }
        for (int i = nPrime; i > 1; --i) {
            sum *= i;
            sum = sum % MOD_BASE;
        }
        return (int) sum;
    }

    private void findAllPrime(int[] numberClass) {
        numberClass[0] = NORMAL;
        numberClass[1] = NORMAL;
        numberClass[2] = PRIME;
        int n = numberClass.length - 1;
        int i = 2;
        while (i < n) {
            int k = 2;
            int j = i * k;
            while (j <= n) {
                numberClass[j] = NORMAL;
                ++k;
                j = i * k;
            }
            ++i;
            while (i < n && numberClass[i] == NORMAL) {
                ++i;
            }
            if (i < n) {
                numberClass[i] = PRIME;
            }
        }
    }
}
